package class09;

import class09.LinkedTools.*;

import java.util.Stack;

/**
 * <a href="https://leetcode.cn/problems/palindrome-linked-list/">234. 回文链表</a>
 */
public class Code02_IsPalindromeList {

    // 利用栈来判断，额外空间复杂度O(N)
    public static boolean isPalindrome1(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode p = head;
        while (p != null) {
            stack.push(p);
            p = p.next;
        }
        p = head;
        while (p != null) {
            if (p.value != stack.pop().value) {
                return false;
            }
            p = p.next;
        }
        return true;
    }

    // 利用快慢指针和反转链表实现额外空间复杂度O(1)实现验证回文链表
    public static boolean isPalindrome2(ListNode head) {
        // 首先分析两种情况
        // 1 奇数个结点，那么慢指针直接是来到中间结点
        // 2 偶数个结点，那么慢指针需要来到中间结点的上一个结点
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 接下来就是反转中间结点后面的链表
        // 首先记录一下当前中间结点的下一个结点，作为后面链表的头结点
        ListNode rightHead = slow.next;
        // 记录好后，就可以把中间结点的下一个结点指向空
        slow.next = null;
        // 接下来就是反转后面链表操作
        // 需要一个指针记录一下前一个结点，头结点的前一个结点是null
        ListNode prev = null;
        // 还需要一个指针记录当前结点的下一个结点
        ListNode next;
        // 做完上面操作后，就可以开始反转操作，rightHead可以充当当前指针进行操作
        while (rightHead != null) {
            next = rightHead.next;  // 记录一下当前结点的下一个位置
            rightHead.next = prev;  // 把当前指针的next指向上一结点
            prev = rightHead;  // 上一结点指回当前结点
            rightHead = next;  // 当前结点到下一个结点去，后面重复这几步操作
        }
        // 反转完成后，当前prev指针充当着到反转后链表的头结点，可以依次和左边的链表进行比较
        // 在这里不去动prev指针，为了后续用来恢复链表，所以在这里利用rightHead去比较是否是回文
        rightHead = prev;
        // 开始判断链表是否是回文
        ListNode leftHead = head;  // 左边头结点
        boolean result = true;
        // 判断的时候，只需要判断左边链表是否为空的情况
        while (leftHead != null && rightHead != null) {
            if (leftHead.value != rightHead.value) {
                result = false;
                break;
            }
            leftHead = leftHead.next;
            rightHead = rightHead.next;
        }
        // 比较完成后，开始恢复链表，下面为了变量可读性高，重新设置一下变量含义
        rightHead = prev;  // rightHead充当反转链表的头结点
        prev = null;  // prev设置为上一结点
        // next结点不需要重置，因为在上面反转的时候，next结点就是指向为空的，并且在下面循环中也会重新指向
        while (rightHead != null) {
            next = rightHead.next;
            rightHead.next = prev;
            prev = rightHead;
            rightHead = next;
        }
        // 最后要将中间结点指向反转链表的头结点，中间结点是开头记录的slow结点，直接将slow结点的next指向上面prev结点即可
        // 为什么可以直接指向prev，因为上面的prev结点经过反转操作，最后是指向反转链表的头结点
        slow.next = prev;
        // 打印看看是否有还原好链表
        ListNode p = head;
        while (p != null) {
            System.out.printf("%d ", p.value);
            p = p.next;
        }
        // 返回是否是回文链表的结果
        return result;
    }

    public static void main(String[] args) {
        ListNode li1 = LinkedTools.stringToListNode("[1,2,3,4,4,3,2,1]");
        ListNode li2 = LinkedTools.stringToListNode("[1,2,3,4,3,2,1]");
        ListNode li3 = LinkedTools.stringToListNode("[1,4,3,4,3,2,1]");
        System.out.println(isPalindrome2(li1));
        System.out.println(isPalindrome2(li2));
        System.out.println(isPalindrome2(li3));
        System.out.println();
    }
}
